typedef int StackDataType;

typedef struct StackNode
{
	StackDataType* _stack;
	int _capacity;
	int _top;
}Stack;

void StackInit(Stack* st);
void StackPush(Stack* st, StackDataType data);
int StackPop(Stack* st);
StackDataType StcakTop(Stack* st);
int StackSize(Stack* st);
int StackEmpty(Stack* st);
void StackDestory(Stack* st);

void StackInit(Stack* st)
{
	st->_stack = NULL;
	st->_capacity = 0;
	st->_top = 0;
}
void StackPush(Stack* st, StackDataType data)
{
	assert(st);
	if (st->_capacity == st->_top)
	{
		int newCapacity = st->_capacity == 0 ? 4 : 2 * st->_capacity;
		st->_stack = (StackDataType*)realloc(st->_stack, newCapacity * sizeof(StackDataType));
		st->_capacity = newCapacity;
	}
	st->_stack[st->_top] = data;
	st->_top++;
}
int StackPop(Stack* st)
{
	assert(st);
	assert(st->_top);
	int tmp = StcakTop(st);
	st->_top--;
	return tmp;
}
StackDataType StcakTop(Stack* st)
{
	assert(st);
	return st->_stack[st->_top - 1];
}
int StackSize(Stack* st)
{
	assert(st);
	return st->_top;
}
int StackEmpty(Stack* st)
{
	assert(st);
	if (st->_top == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
void StackDestory(Stack* st)
{
	assert(st);
	if (st->_stack != NULL)
	{
		free(st->_stack);
	}
	st->_capacity = st->_top = 0;

}


typedef struct {
	Stack* s1;
	Stack* s2;
} MyQueue;


MyQueue* myQueueCreate() {
	MyQueue* newQueue = (MyQueue*)malloc(sizeof(MyQueue));
	newQueue->s1 = (Stack*)malloc(sizeof(Stack));
	newQueue->s2 = (Stack*)malloc(sizeof(Stack));
	StackInit(newQueue->s1);
	StackInit(newQueue->s2);
	return newQueue;
}

void myQueuePush(MyQueue* obj, int x) {
	StackPush(obj->s1, x);
}

int myQueuePop(MyQueue* obj) {
	if (StackEmpty(obj->s2))
	{
		while (!StackEmpty(obj->s1))
		{
			StackPush(obj->s2, StackPop(obj->s1));
		}
	}
	return StackPop(obj->s2);
}

int myQueuePeek(MyQueue* obj) {
	if (StackEmpty(obj->s2))
	{
		while (!StackEmpty(obj->s1))
		{
			StackPush(obj->s2, StackPop(obj->s1));
		}
	}
	return StcakTop(obj->s2);
}

bool myQueueEmpty(MyQueue* obj) {
	return StackEmpty(obj->s1) && StackEmpty(obj->s2);
}

void myQueueFree(MyQueue* obj) {
	StackDestory(obj->s1);
	StackDestory(obj->s2);
	free(obj->s1);
	free(obj->s2);
	free(obj);
}
